package com.hanxiaozhang.stackandqueue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * 〈一句话功能简述〉<br>
 * 〈栈和队列面试题〉
 *
 * @author hanxinghua
 * @create 2021/9/7
 * @since 1.0.0
 */
public class StackQueueTopic {

    public static void main(String[] args) {
        // 补充知识点：Stack中peek与Pop的区别
//        peekAndPop();

        // topic1();

        // topic2();

        topic3();


    }

    /**
     * 如何使用队列结构实现栈结构？
     *
     */
    private static void topic3() {
        QueueImplStack stack = new QueueImplStack();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }


    /**
     * 两个队列实现栈
     */
    public static class QueueImplStack {

        private Queue<Integer> queue;
        private Queue<Integer> help;

        public QueueImplStack() {
            queue = new LinkedList<>();
            help = new LinkedList<>();
        }


        public void push(Integer value) {
            queue.offer(value);
        }

        public Integer pop() {
            while (queue.size() > 1) {
                help.offer(queue.poll());
            }
            Integer value = queue.poll();
            Queue<Integer> temp = queue;
            queue = help;
            help = temp;
            return value;
        }

    }


    /**
     * 如何使用栈结构实现队列结构？
     * 思路：准备两个栈，一个push栈和pop栈。设计一个私有方法 pushToPop()：只要pop栈为空时，
     * 就允许把push栈中的元素导入pop中。在offer()中push后调用pushToPop()。
     * 在poll()中pop之前调用pushToPop()。
     */
    private static void topic2() {
        StackImplQueue queue = new StackImplQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.poll());
        queue.offer(4);
        System.out.println(queue.poll());
    }


    /**
     * 两个栈实现队列
     */
    public static class StackImplQueue {

        private Stack<Integer> stackPush;

        private Stack<Integer> stackPop;

        public StackImplQueue() {
            stackPush = new Stack<>();
            stackPop = new Stack<>();
        }


        /**
         * push栈向pop栈倒入数据
         */
        private void pushToPop() {
            if (stackPop.empty()) {
                while (!stackPush.empty()) {
                    stackPop.push(stackPush.pop());
                }
            }

        }

        /**
         * 进队
         *
         * @param value
         */
        public void offer(Integer value) {
            stackPush.push(value);
            pushToPop();
        }

        /**
         * 出队
         *
         * @return
         */
        public Integer poll() {
            if (stackPop.empty() && stackPush.empty()) {
                throw new RuntimeException("Queue is null");
            }
            pushToPop();
            return stackPop.pop();
        }


    }

    /**
     * 实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能：
     * pop push getMIn操作的时间复杂度都是O(1)
     * 设计的栈类型可以使用现成的栈结构
     */
    private static void topic1() {
        MinStack myStack = new MinStack();
        myStack.push(5);
        System.out.println("min is " + myStack.getMin());
        myStack.push(10);
        System.out.println("min is " + myStack.getMin());
        myStack.push(3);
        System.out.println("min is " + myStack.getMin());
        myStack.push(4);
        System.out.println("min is " + myStack.getMin());
        myStack.push(4);
        System.out.println("min is " + myStack.getMin());
        System.out.println("--------");
        myStack.pop();
        System.out.println("min is " + myStack.getMin());
        myStack.pop();
        System.out.println("min is " + myStack.getMin());
        myStack.pop();
        System.out.println("min is " + myStack.getMin());
    }

    /**
     * 自定义栈
     */
    public static class MinStack extends Stack<java.lang.Integer> {

        private Stack<java.lang.Integer> stack;

        public MinStack() {
            stack = new Stack<>();
        }

        @Override
        public java.lang.Integer pop() {
            java.lang.Integer value = super.pop();
            if (value.equals(getMin())) {
                stack.pop();
            }
            return value;
        }

        @Override
        public java.lang.Integer push(java.lang.Integer item) {
            if (stack.empty()) {
                stack.push(item);
            } else if (item <= getMin()) {
                stack.push(item);
            }
            return super.push(item);
        }

        public java.lang.Integer getMin() {
            return stack.peek();
        }

    }


    /**
     * peek与pop的区别：
     */
    private static void peekAndPop() {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        System.out.println("first peek() is " + stack.peek());
        System.out.println("second peek() is " + stack.peek());
        System.out.println("first pop() is " + stack.pop());
        System.out.println("second pop() is " + stack.pop());
    }
}
